package com.lhcai.lc.category.binarysearch;

/**
 * 540. 有序数组中的单一元素
 *
 * @author liuhuaicai
 * @since 2024-11-10 17:36
 */
public class Lc540 {
    public static void main(String[] args) {
        Lc540 lc540 = new Lc540();
        System.out.println(lc540.singleNonDuplicate(new int[]{1, 1, 2, 3, 3, 4, 4, 8, 8}));
    }

    public int singleNonDuplicate(int[] nums) {
        // 数组长度必为奇数，且有序  二分查找
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            // mid + 2 * (mid % 2) - 1 偶数 则获取前一位，奇数，获取后一位 这是右侧
            // 1 1 2 2 3 4 4
            // 0 1 2 3 4 5 6 左侧 偶 + 奇 右侧，奇 + 偶
            if (nums[mid] == nums[mid + 2 * (mid % 2) - 1]) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return nums[l];
    }
}
